Search results for "LALR parser"
showing 2 items of 2 documents
Testing Grammars for Parsability
1990
In the preceding chapters we have studied in detail the major methods of deterministic context-free parsing: strong LL(k) parsing (Chapter 5), simple precedence parsing (Chapter 5), canonical LR(k) parsing, LALR(k) parsing, and SLR(k) parsing (Chapters 6 and 7), and canonical LL(k) parsing (Chapter 8). Each of these methods induces a class of grammars that are “parsable” using that method, that is, a class of grammars for which a deterministic parser employing that method can be constructed. For example, the LL(k) grammars constitute the class of grammars parsable by the LL(k) parsing method. By definition, a context-free grammar is an LL(k) grammar if and only if its canonical LL(k) parser…
Construction and Implementation of LR(1) Parsers
1990
This chapter is devoted to the practical issues involved in the construction and use of deterministic LR(1) parsers. We shall show how the practical versions of LR (1) parsers, most notably the LALR (1) parsers, can be constructed efficiently, and we shall present methods for encoding LR(1) parsers as efficient RAM programs. Two versions of RAM program implementation are considered: in the first implementation the parsing program is table-driven, that is, the rules of the parser are encoded in a two-dimensional array which is simulated by a program body; in the other implementation the tabular information is further transformed into a set of program statements.